package demo.practice.uf;

/**
 * 快速合并
 */
public class UFQuickUnion {

    int[] parent;

    public UFQuickUnion(int size) {
        parent = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }

    public int findP(int x) {//查询操作，其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        while (parent[x] != x)//一直搜索到根节点
            x = parent[x];

        return x;
    }

    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            parent[ap] = bp;//让其中一个节点的根节点 指向  另外一个节点的根节点
        }
    }

    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }

}
